// LeetCode 主站 Problem Nr. 590: N叉树的后序遍历

package main

import (
	"github.com/saint-yellow/think-leetcode/ds"
)

type Node = ds.NAryNode[int]

func postOrder(root *Node) []int {
    // return method1(root)

	result := make([]int, 0)
	method2(root, &result)
	return result
}

func method1(root *Node) []int {
	var dfs func(root *Node, result *[]int)
	dfs = func(root *Node, result *[]int) {
		if root == nil {
			return
		}

		if root.Children != nil {
			for _, child := range root.Children {
				dfs(child, result)
			}
		}
		*result = append(*result, root.Val)
	}

	result := make([]int, 0)
	dfs(root, &result)
	return result
}

func method2(root *Node, result *[]int) {
	if root == nil {
		return
	}

	for _, node := range root.Children {
		method2(node, result)
	}
	*result = append(*result, root.Val)
}

func method3(root *Node) []int {
	result := []int{}
	if root == nil {
		return result
	}

	stack := make([]*Node, 0)
	stack = append(stack, root)
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:]
		if node == nil {
			node = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			result = append(result, node.Val)
			continue
		}
		stack = append(stack, node)
		stack = append(stack, nil)

		if node.Children != nil {
			for i := len(node.Children) - 1; i >= 0; i-- {
				child := node.Children[i]
				if child != nil {
					stack = append(stack, child)
				}
			} 
		}
	}

	return result
}
